/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-15
 * Time: 22:50
 */
public class Solution {
//     数学分析
//     一直朝着 target 走,
//     1. 如果正好走到, 那么就是答案
//     2. 越过 偶数距离: 比如 2, 那么将第一步 反向, 比如 8, 就将第四步反向
//     3. 越过 奇数距离 ① 多走一次就变偶数, 变成情况 2, ② 多走一次还是奇数, 那就再多走一次必变偶数, 又变成情况 2
//     问题: 为什么 越过偶数距离, 让反向一步就行了 ? 反向的话就差了两倍,所以能正好消除越过的这几步
//     为什么按照这种方法走次数最少 ? 因为反向差两倍,只能处理偶数的情况, 所以必须变为偶数,所以这是次数最少的
    public int reachNumber(int target) {
        if (target < 0) {
            target = -target;
        }
        int pos = 0;
        int step = 1;
        while (pos < target || (pos-target) % 2 != 0) {
            pos += step;
            step++;
        }
        return step-1;
    }


    /**
     *  知道上面的原理后, 就可以使用二分查找找 step 了, 不用再一步一步的加了
     * @param target
     * @return
     */
    public int reachNumber2(int target) {
        if (target < 0) {
            target = -target;
        }
        int left = 1;
        int right = target;
        // 二分查找, 找到第一次越过(正好走到的那一步)
        while (left < right) {
            int mid = ((right-left)>>1) + left;
            if (((long)(mid)*(mid+1)/2) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int sum = left*(left+1)/2;
        int dist = sum - target;
        // 最后要分为 正好差偶数步, 差奇数步 多走 1 次还是 2 次变偶数步, 情况与上面的一样
        return dist%2==0 ? left : left+1+left%2;
    }

}
